package com.salim.leetcode.$240;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 这道题还有一种从右上开始往左下走的解法 大于就往下 小于就往左
 * 而我的解法是沿着左对角线走
 */
public class SearchA2DMatrixII {
    public boolean searchMatrix(int[][] matrix, int target) {

        //对角线查询
        //然后分别二分
        //如果触线 贴边运动
        //只要对应起点的两条或一条边所遍历到的最小点比target小 且没有找到target 那么就可以继续运动
        //简单点数说 除非对应起点及生效的两条或一条边的最小值大于target 那么就结束范围

        int row = matrix.length;
        int column = matrix[0].length;
        int walkLength = Math.max(row,column);

        if(matrix[0][0]==target){
            return true;
        }

        if(row==1){
            return binarySearchRow(matrix,column-1,0,target)==0;
        }else if(column==1){
            return binarySearchColumn(matrix,row-1,0,target)==0;
        }

        int rResult;
        int cResult;
        //到这里默认最小2*2
        for(int i=0;i<walkLength;i++){
            //如果能往右下走 判断右下是否大于target 如果是 行列二分查找 并往右下走
            //如果只能往右走 判断右是否大于target 如果是 列二分查找 并往右走
            //如果只能往下走 判断下是否大于target 如果是 行二分查找 并往下走
            if(i+1<row && i+1<column){
                rResult = binarySearchRow(matrix,i+1,i+1,target);
                cResult = binarySearchColumn(matrix,i+1,i+1,target);
                if(rResult==0||cResult==0){
                    return true;
                }else if(rResult==-2&&cResult==-2){
                    return false;
                }
            }else if(i+1<row){
                rResult = binarySearchRow(matrix,column-1,i+1,target);
                if(rResult==0){
                    return true;
                }else if(rResult==-2){
                    return false;
                }
            }else if(i+1<column){
                cResult = binarySearchColumn(matrix,row-1,i+1,target);
                if(cResult==0){
                    return true;
                }else if(cResult==-2){
                    return false;
                }
            }else {
                return false;
            }
        }
        return false;
    }

    public static void main(String[] args){
        SearchA2DMatrixII searchA2DMatrixII = new SearchA2DMatrixII();
//        int[][] a = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
//        searchA2DMatrixII.searchMatrix(a,20);
        int[][] a = {{1,4},{2,5}};
        searchA2DMatrixII.searchMatrix(a,1);
    }

    //-1没有
    //-2应当终止
    //0有
    //二分查找行
    public int binarySearchRow(int[][] matrix,int end,int row,int target){
        if(matrix[row][0]>target){
            return -2;
        }

        int low = 0;
        int high = end;
        while (low<=high){
            int mid =low + (high -low)/2;
            if(target<matrix[row][mid]){
                //左
                high = mid-1;
            }else if(target>matrix[row][mid]){
                low = mid+1;
            }else{
                return 0;
            }
        }
        return -1;
    }

    public int binarySearchColumn(int[][] matrix,int end,int column,int target){
        if(matrix[0][column]>target){
            return -2;
        }

        int low = 0;
        int high = end;
        while (low<=high){
            int mid =low + (high -low)/2;
            if(target<matrix[mid][column]){
                //左
                high = mid-1;
            }else if(target>matrix[mid][column]){
                low = mid+1;
            }else{
                return 0;
            }
        }
        return -1;
    }
}
